//本解法已通过LeetCode测试，但复杂度过高
class Solution {
public:
	string longestPalindrome(string s) {
		if (s.length() == 0) return "";
		if (s.length() == 1) return s;
		double index = 0;
		int maxLength = 1;
		for (int i = 1; i <= s.length() - 1; i++) {
			int length;
			length = palindromeLength(s, i - 0.5);
			if (length > maxLength) {
				index = i;
				maxLength = length;
			}
			length = palindromeLength(s, i);
			if (length > maxLength) {
				index = i;
				maxLength = length;
			}
		}
		if ((int)index == index) {
			return s.substr(index - maxLength / 2, maxLength);
		}
		else {
			return s.substr((int)index - maxLength / 2 + 1, maxLength);
		}
	}
private:
	//以index为中心的最长回文串的长度
	int palindromeLength(const string& s, int index) {
		int i = 1;
		while (index - i >= 0 && index + i <= s.length() - 1) {
			if (s[index + i] == s[index - i]) i++;
			else break;
		}
		return 1 + 2 * (i - 1);
	}
	int palindromeLength(const string& s, double index) {
		int i = 0;
		while ((int)(index - 0.5) - i >= 0 && (int)(index + 0.5) + i <= s.length()) {
			if (s[(int)(index - 0.5) - i] == s[(int)(index + 0.5) + i]) i++;
			else break;
		}
		return 2 * i;
	}
};